package cn.com.mdx.sort.heapsort.priorityqueue;

import cn.com.mdx.sort.SortUtils;

import java.util.Random;

/**
 * <p>
 *
 * @author ：huangy
 * @date ：Created in 2020/10/16 3:22 下午
 */
@SuppressWarnings(value = {"unchecked"})
public class BinaryHeapMinPQ<Key extends Comparable<Key>> {
    /**
     * 点集
     */
    private final Key[] pq;

    /**
     * 容器容量
     */
    private int N;

    public BinaryHeapMinPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity];
    }

    /**
     * @param key 数据
     * @return void
     * @Author huangy
     * @description //TODO 向二叉堆中插入数据
     * @date 9:44 上午 2020/10/16
     **/
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }

    /**
     * @param index 要上浮的节点位置
     * @return void
     * @Author huangy
     * @description //TODO 节点上浮
     * @date 9:45 上午 2020/10/16
     **/
    public void swim(int index) {
        while (index > 1 && SortUtils.great(pq[index / 2], pq[index])) {
            SortUtils.exChange(pq, index, index / 2);
            index = index / 2;
        }
    }

    /**
     * @return max 最大节点
     * @Author huangy
     * @description //TODO 删除最大节点
     * @date 10:18 上午 2020/10/16
     **/
    public Key delMax() {
        //获取最大节点
        Key max = pq[1];
        //最大节点和最小节点交换
        SortUtils.exChange(pq, 1, N--);
        //节点下沉
        sink(1);
        pq[N + 1] = null;
        return max;
    }

    /**
     * @param index 要下沉的节点位置
     * @return void
     * @Author huangy
     * @description //TODO 节点下沉
     * @date 10:19 上午 2020/10/16
     **/
    public void sink(int index) {
        while (2 * index <= N) {
            //节点index扩大两倍(子节点位置)
            int j = 2 * index;
            if (j < N && SortUtils.great(pq[j], pq[j + 1])) j = j + 1;
            if (!SortUtils.great(pq[index], pq[j])) break;
            SortUtils.exChange(pq, index, j);
            index = j;
        }
    }

    /**
     * @return Key 最大节点
     * @Author huangy
     * @description //TODO 获取最大节点
     * @date 10:35 上午 2020/10/16
     **/
    public Key max() {
        if (!isEmpty()) return pq[1];
        return null;
    }

    /**
     * @return boolean true 表示为空 false 表示不为空
     * @Author huangy
     * @description //TODO 判断容器是否为空
     * @date 10:38 上午 2020/10/16
     **/
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * @return void
     * @Author huangy
     * @description //TODO 打印数组
     * @date 10:41 上午 2020/10/16
     **/
    private void printArray() {
        if (!isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (i != N) System.out.print(pq[i] + "|");
                else System.out.println(pq[i]);
            }
        }
    }

    public static void main(String[] args) {
        int N = 16;
        Random random = new Random();
        BinaryHeapMinPQ<Integer> binaryHeapMinPQ = new BinaryHeapMinPQ<>(N + 1);
        //向容器中插入数据
        for (int i = 0; i < N; i++) {
            binaryHeapMinPQ.insert(random.nextInt(N));
            binaryHeapMinPQ.printArray();
        }
        //从容器中取出数据
        for (int i = 0; i < N; i++) {
            System.out.println(binaryHeapMinPQ.delMax());
            binaryHeapMinPQ.printArray();
        }
    }
}
